package pers.vic.basics.sort;

import java.util.Arrays;

/**
 * @author Vic.xu
 * @description:希尔排序·高级排序
 * @date: 2020/10/23 0023 17:01
 */
public class ShellSort {

    /*
    希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
     */

    /**
     * 希尔排序
     * 最初分组步长问为长度除2，直至步长为1.
     * 后经Knuth改良，步长修改为 step = step/3 + 1 ()
     * 1. 分组，
     * 2. 组内排序
     * 3.调整步长，重复1,2，直至步长为1
     */
    public static void sort(int[] arr) {
        int len = arr.length;
        int step = len / 2;

        // 定步长   len / 2 至步长为1
        while (step > 0) {
            //使用插入排序 调整 同步长组成的数组的顺序
            for (int i=step; i<len; i++) {
                int temp = arr[i];
                int j = i;
                while (j>=step && arr[j-step] >temp) {
                    arr[j] = arr[j-step];
                    j -= step;
                }
                arr[j] = temp;
            }
            step /= 2;
        }

    }

    public static void main(String[] args) {
        int[] arr = {9, 7, 5, 3, 1, 2, 4, 8, 0};
        sort(arr);
        System.out.println(Arrays.toString(arr));

    }
}
